package cn.chrilwe.pigpig.im.words;

import java.util.ArrayList;
import java.util.List;

import org.springframework.util.StringUtils;

/**
 *  kmp算法
 *  移动的距离 =  匹配的字符数量  - next值
 * @author chrilwe
 * 2020-8-2
 */
public class Kmp {

	public static int findFirstIndex(String smallStr, String bigStr) {
		int length = bigStr.length();
		char[] bigCharArray = bigStr.toCharArray();
		char[] smallCharArray = smallStr.toCharArray();
		
		int[] next = next(smallStr);
		
		int index = 0;
		String str = "";
		int j = index;
		while(true) {
			if((bigCharArray.length - index) < smallCharArray.length) {
				return 0;
			}
			str = "";
			j = index;
			for (int i = 0; i < smallCharArray.length; i++) {
				char ch = bigCharArray[j];
				char ch1 = smallCharArray[i];
				str += ch1;
				if(!(ch+"").equals(ch1+"")) {
					index += (j - next[j])+1;
					break;
				} else {
					j++;
				}
				if(i==smallCharArray.length-1 && (smallCharArray[smallCharArray.length-1]+"").equals(bigCharArray[index+smallCharArray.length]+"")) {
					return index;
				}
			}
		}
	}
	
	protected static int[] next(String str) {
		int length = str.length();
		char[] charArray = str.toCharArray();
		char[] newArray = new char[length];
		
		int[] next = new int[length];
		
		for(int i = 0; i < length; i++) {
			if(length == 1) {
				next[i] = 0;
				continue;
			}
			
			List<String> preList = new ArrayList<String>();
			List<String> endList = new ArrayList<String>();

			char tail = charArray[i];
			String end = "";
			for(int j=i; j>0; j--) {
				end = charArray[j] + end;
				endList.add(end);
			}
			
			String pre = "";
			char head = charArray[0];
			for(int j=0; j<i; j++) {
				pre += charArray[j];
				preList.add(pre);
			}
			
			int currentNextValue = 0;
			for(int j=0; j<preList.size(); j++) {
				String p = preList.get(j);
				for(int m=0; m<preList.size(); m++) {
					String e = endList.get(m);
					if(p.equals(e)) {
						currentNextValue += p.length();
					}
				}
			}
			
			next[i] = currentNextValue;
		}
		return next;
	}
	
	public static void main(String[] args) {
		int index = Kmp.findFirstIndex("AB", "SCDABD");
		System.out.println(index);
	}
}
